package com.leetcode.LeetCode精选TOP面试题;

import com.leetcode.common.model.TreeNode;
import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author 覃国强
 * @date 2022-06-20 18:09
 */
public class 题库_0124_二叉树中的最大路径和 {

  public static void main(String[] args) {
    TreeNode a = new TreeNode(1);
    TreeNode b = new TreeNode(2);
    TreeNode c = new TreeNode(3);

    a.left = b;
    a.right = c;

    Solution solution = new Solution();
    int sum = solution.maxPathSum(a);
    System.out.println(sum);
  }


  static
  class Solution {

    private int answer;

    public int maxPathSum(TreeNode root) {
      answer = Integer.MIN_VALUE;
      maxPathSumCurNode(root, new HashMap<>());
      return answer;
    }

    private int maxPathSumCurNode(TreeNode node, Map<TreeNode, Integer> maxSums) {
      if (node == null) {
        return 0;
      }
      if (maxSums.containsKey(node)) {
        return maxSums.get(node);
      }
      int leftSum = Math.max(maxPathSumCurNode(node.left, maxSums), 0);
      int rightSum = Math.max(maxPathSumCurNode(node.right, maxSums), 0);

      answer = Math.max(answer, node.val + leftSum + rightSum);

      return node.val + Math.max(leftSum, rightSum);
    }

    public int maxPathSum1(TreeNode root) {
      if (root == null) {
        return 0;
      }

      // 统计每一个节点的父节点
      Map<TreeNode, TreeNode> fathers = generateFatherRelation(root);
      Set<TreeNode> marks = new HashSet<>();
      Map<TreeNode, Integer> maxSums = new HashMap<>();

      Deque<TreeNode> queue = new ArrayDeque<>();
      queue.add(root);
      while (!queue.isEmpty()) {
        root = queue.remove();
        marks.add(root);
        helper(root, root, 0, marks, fathers, maxSums);
        marks.remove(root);
        if (root.left != null) {
          queue.add(root.left);
        }
        if (root.right != null) {
          queue.add(root.right);
        }
      }

      return maxSums.values().stream().max(Comparator.naturalOrder()).orElse(0);
    }

    private Map<TreeNode, TreeNode> generateFatherRelation(TreeNode root) {
      Map<TreeNode, TreeNode> father = new HashMap<>();
      Deque<TreeNode> queue = new ArrayDeque<>();
      queue.add(root);
      while (!queue.isEmpty()) {
        root = queue.remove();
        if (root.left != null) {
          father.put(root.left, root);
          queue.add(root.left);
        }
        if (root.right != null) {
          father.put(root.right, root);
          queue.add(root.right);
        }
      }
      return father;
    }

    private void helper(TreeNode source, TreeNode node, int sum, Set<TreeNode> marks, Map<TreeNode, TreeNode> fathers, Map<TreeNode, Integer> maxSums) {
      // 计算到达当前节点的值
      sum += node.val;
      // 将该值与 source 节点的路径最大值做比较
      Integer maxSum = maxSums.getOrDefault(source, Integer.MIN_VALUE);
      maxSums.put(source, Math.max(sum, maxSum));

      // 走向左节点
      if (node.left != null && !marks.contains(node.left)) {
        // 将左节点标记为已经过
        marks.add(node.left);
        helper(source, node.left, sum, marks, fathers, maxSums);
        // 恢复左节点标记为未经过
        marks.remove(node.left);
      }

      // 走向右节点
      if (node.right != null && !marks.contains(node.right)) {
        marks.add(node.right);
        helper(source, node.right, sum, marks, fathers, maxSums);
        marks.remove(node.right);
      }

      // 走向父节点
      TreeNode father = fathers.get(node);
      if (father != null && !marks.contains(father)) {
        marks.add(father);
        helper(source, father, sum, marks, fathers, maxSums);
        marks.remove(father);
      }
    }
  }

}
